const { ListNode, LinkedList } = require('../2. 链表/1. 链表基础/1. 建立线性链表.js')
// 给定两个升序链表list1和list2，将其合并为一个升序链表
// 思路，使用虚拟节点，操作cur.next

function mergeTwoLists(list1, list2) {
    let dummyHead = new ListNode(0)
    let cur = dummyHead
    while (list1 && list2) {
        if (list1.val < list2.val) {
            cur.next = list1
            list1 = list1.next
        } else {
            cur.next = list2
            list2 = list2.next
        }
        cur = cur.next
    }
    cur.next = list1 ? list1 : list2
    return dummyHead.next
}

let list1 = new LinkedList([1, 7, 9])
let list2 = new LinkedList([2, 4, 5, 8])
console.log(mergeTwoLists(list1.head, list2.head))